// 重排链表

package Leetcode;

import java.util.ArrayList;
import java.util.List;

class Solution_143_1 {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null)
            return;
        List<ListNode> list = new ArrayList<>();
        ListNode pointer = head;
        // 把链表放在列表中
        while (pointer != null) {
            list.add(pointer);
            pointer = pointer.next;
        }
        // 双指针
        int font = 0;
        int back = list.size() - 1;
        int direction = 1; // 1表示从前向后，-1表示从后向前
        while (font != back) {
            if (direction == 1) {
                direction = -direction;
                list.get(font).next = list.get(back);
                font++;
            } else {
                direction = -direction;
                list.get(back).next = list.get(font);
                back--;
            }
        } // while
        list.get(font).next = null;
    }// recoderList
}

class Solution_143_2 {
    public void reorderList(ListNode head) {
        if (head == null)
            return;
        // 找中间位置
        ListNode mid = middleNode(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null;
        // 反转一半
        l2 = reverseList(l2);
        // 组合两个部分
        mergeList(l1, l2);
    }

    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode node = head.next;
            head.next = pre;
            pre = head;
            head = node;
        }
        return pre;
    }

    // l1.length == l2.length 或 l1.length == l2.length+1
    public void mergeList(ListNode l1, ListNode l2) {
        ListNode node1;
        ListNode node2;
        while (l1 != null && l2 != null) {
            node1 = l1.next;
            node2 = l2.next;

            l1.next = l2;
            l2.next = node1;

            l1 = node1;
            l2 = node2;
        }
    }
}